#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct qie {
    int high;
    int attack;
};

int quickpass(struct qie *a, int i, int j)
{
    struct qie q = a[i];
    int x = q.high;
    
    while (i < j) {
        while (i < j && a[j].high >= x)
            j --;
        a[i] = a[j];

        while (i < j && a[i].high <= x)
            i ++;
        a[j] = a[i];
    }
    a[i] = q;

    return i;
}

void quicksort(struct  qie*a, int i, int j)
{
    int k;

    if (i < j) {
        k = quickpass(a, i, j);
        quicksort(a, i, k-1);
        quicksort(a, k+1, j);
    }
}

int main(int argc, char *argv[])
{
    int i, j, maxA, *t;
    struct qie qq[10];
    
    srandom(time(NULL));
    for (i = 0; i < 10; i++) {
        qq[i].high = random()%1001;
        qq[i].attack = random()%1001;
    }
    
    quicksort(qq, 0, 9);
    for (i = 0; i < 10; i++) {
        printf("%d ", qq[i].high);
    }
    printf("\n");
    for (i = 0; i < 10; i++) {
        printf("%d ", qq[i].attack);
    }
    printf("\n");

    maxA = 1001;
    t = calloc(maxA, sizeof(int));
    for (i = 0; i < 10; i++) {
        for (j = maxA; j >= qq[i].attack; j--) {
            if (t[j-1] < t[qq[i].attack-1]+1)
                t[j-1] = t[qq[i].attack-1]+1;
        }
    }

    printf("max kill %d\n", t[maxA-1]);

    free(t);
    return 0;
}
